\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{listings}
\lstset{
    stepnumber=1,
    language=Lisp
}

% Usage:
% \commandDescription{NAME}{Short description}{arguments}{Description}
\newcommand{\commandDescription}[5]{
    \subsubsection{\texttt{#1}}
    #2
    \paragraph{Arguments}
    #3
    \paragraph{Description}
    #4
}

\title{\LaTeX}
\date{}

\begin{document}

\include{introduction}

\include {lang_reference_core}

\section{Basic Data Structures}

\subsection{Linked Lists}

\subsection{Last In - First Out - The Stack}

\subsection{Dictionaries - The Hash Table}


\section{Symbols}

\subsection{\texttt{NIL}}

\texttt{NIL} is general identified with the NULL-pointer. Whenever a
NULL-Pointer is encountered, it is interpreted to represent \texttt{NIL}.


\section{\texttt{lambda}}

\texttt{lambda} is represented by a structure that contains 

\begin{enumerate}
\item A list of symbols. These symbols will be inserted into the current symbol
table with the parameters of the lambda call as values. 
\item A pointer to a Block of code to be executed when being called.
\end{enumerate}

Whenever a lambda expression is called with parameters, the following steps will
be performed:

\begin{enumerate}
\item  the parameters' values are inserted into the current lookup table  with the 
symbols of the lambda function. If the symbols already exist within the table,
the symbols original values have to be saved.
\item The lambda values code block is executed.
\item The symbols original values are restored.
\end{enumerate}


\section{Symbol Tables}

\begin{enumerate}
\item There is one global Symbol table. This table contains \texttt{NIL} etc.
\item Other symbol tables can be created on demand, for example by package.
These symbol tables are inserted into the current symbol table.
\item If a package is entered, the current package is pushed onto a stack and
the symbol table of the package becomes the new one.
\end{enumerate}

Lookups are performed via

\begin{enumerate}
\item the symbol is looked up in the current lookup table.
\item If not found, the symbol table stack is searched for.
\item A name like \texttt{part1::part2::part3...} is split up into its parts. Then,
\texttt{part1} is looked up just as a normal symbol. If it does not resolve to a symbol
table, an error is produced. If it resolves to a symbol table, the other parts
\texttt{part2}, \texttt{part3} etc are looked up within this lookup table.
\end{enumerate}


\section{Input/Output}

Uttmost principle should be that if a expression is printed out, its textual
representation, fed back into the reader, should yield a equivalent expression,
that is the following relation should hold:

({\texttt READ} ({\texttt COERCE} {\texttt 'STRING} {\texttt EXPRESSION})) $\equiv$ {\texttt EXPRESSION}

\section{Implementation}

\subsection{Garbage Collection}

\subsection{Strings}

\include{strings}

\section{Optimisations}

\subsection{Memory Preallocation}

\subsubsection{Benchmark}


Compiled the REPL twice, once with memory preallocation enabled, once with
memory preallocation disabled.
Then started both REPLs in parallel, and evaluated one form subsequently in the
one REPL, then the other, repeated this several times.
The form to be evaluated is

\begin{verbatim}
    (CONS (CONS (CONS (CONS (CONS 
      (CONS (CONS (CONS (CONS (CONS 
        (CONS (CONS (CONS (CONS (CONS 
          (CONS (CONS (CONS (CONS (CONS 
            (CONS (CONS 0 1) 2)
          3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 
        13) 14) 15) 16) 17) 
      18) 19) 20) 21) 22)
\end{verbatim}

Results are shown in table \ref{tbl:BMResultsMemPreallocation}.
As you can see, for this example we gain about 9\% of speed.
We will not ignore the fact that this example has been tailored for making
abundand memory requests.

\begin{table}
    \centering
    \begin{tabular}{r|c|c}
           & With  & Without \\
        \hline 
         1 & 22038 & 24153 \\
         2 & 22157 & 24841 \\
         3 & 22204 & 24377 \\
         4 & 22238 & 25251 \\
         5 & 22315 & 24141 \\
         6 & 22815 & 24792 \\
         7 & 22146 & 24134 \\
         8 & 22268 & 24498 \\
         9 & 21969 & 24489 \\
        10 & 21720 & 24750 \\
        \hline
        summary & 221870 & 245426 \\
        \hline
        average & 22187  & 24543
    \end{tabular}
    \caption{\label{tbl:BMResultsMemPreallocation} Ticks measured for evaluating
        the form given in the text, left with memory preallocation enabled, on
    the right disabled.}
\end{table}


\subsection{Packed Expression Structure}

\subsubsection{Benchmark}


\begin{table}
    \centering
    \begin{tabular}{r|c|c}
           & flat  & packed \\
        \hline 
         1 & 358995 & 714173 \\
         2 & 506777 & 360570 \\
         3 & 734729 & 444427 \\
         4 & 719196 & 664277 \\
         5 & 730034 & 401226 \\
         6 & 592128 & 460916 \\
         7 & 673055 & 383550 \\
         8 & 724243 & 741072 \\
         9 & 486136 & 361164 \\
        10 & 728938 & 732850 \\
        \hline
        summary & 6254231 & 732850 \\
        \hline
        average & & 
    \end{tabular}
    \caption{\label{tbl:BMResultsExpressionFormat} Ticks measured for performing
        test-eval, left with the initial, flat structure, on
    the right with the packed format.}
\end{table}
\end{document}
